package tulingxueyuan117;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 快速升序排序（很重要）
 */
public class p37_归并排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        int[] res = mergeSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }

    public static int[] mergeSort(int[] nums) {
        if(nums.length<2) return nums;  // 递归终止条件
        int mid = nums.length/2;
        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid, nums.length);
        return merge(mergeSort(left), mergeSort(right));
    }
    public static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length+right.length];
        for(int index=0, i=0, j=0; index<result.length; index++){
            if(i>=left.length){
                result[index] = right[j++];
            }
            else if(j>=right.length){
                result[index] = left[i++];
            }
            else if(left[i]>right[j]){
                result[index] = right[j++];
            }
            else {
                result[index] = left[i++];
            }
        }
        return result;
    }
}
